#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
const int maxn=100001;
LL phi[maxn],prime[10000],pp[20];
int no;
bool bo[maxn];
int p=0;
void ELUR()
{
	for(int i=1;i<maxn;i++)phi[i]=i;
	for(int i=2;i<maxn;i+=2)phi[i]/=2;
	for(int i=3;i<maxn;i+=2)
		if(phi[i]==i)
		{
			for(int j=i;j<maxn;j+=i)
				phi[j]=phi[j]/i*(i-1);
		}
	memset(bo,0,sizeof(bo));
	bo[0]=bo[1]=1;

	for(int i=2;i<maxn;i++)
	{
		if(!bo[i])prime[p++]=i;
		for(int j=i;j<maxn;j+=i)
			bo[j]=1;
	}
}

LL inclusion_exclusion(int idx,int b,int n)
{
	LL res=0,t;
	for(int i=idx;i<no;i++)
	{
		t=b/pp[i];
		res+=t-inclusion_exclusion(i+1,t,n);
	}
	return res;
}
int main()
{
	ELUR();
	int t,a,b,d,k;
	cin>>t;
	for(int cas=1;cas<=t;cas++)
	{
		cin>>a>>b>>a>>d>>k;
		if(k==0)
		{cout<<"Case "<<cas<<": 0\n";continue;}
		b/=k;d/=k;
		if(b>d){a=b;b=d;d=a;}

		LL ans=0;
		for(int i=1;i<=b;i++)
			ans+=phi[i];
		for(int i=b+1;i<=d;i++)
		{
			no=0;
			a=i;
			for(int j=0;j<p&&prime[j]*prime[j]<=a;j++)
			if(!(a%prime[j]))
			{
				pp[no++]=prime[j];
				do
					a/=prime[j];
				while(a%prime[j]==0);

			}
			if(a>1)
				pp[no++]=a;
			ans+=b-inclusion_exclusion(0,b,i);
		}
		cout<<"Case "<<cas<<": "<<ans<<"\n";
	}
}

